{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find All Good Indices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: goodIndices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到所有好下标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;和一个正整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>对于&nbsp;<code>k &lt;= i &lt; n - k</code>&nbsp;之间的一个下标&nbsp;<code>i</code>&nbsp;，如果它满足以下条件，我们就称它为一个&nbsp;<strong>好</strong>&nbsp;下标：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>下标 <code>i</code> <strong>之前</strong> 的 <code>k</code>&nbsp;个元素是 <strong>非递增的</strong>&nbsp;。</li>\n",
    "\t<li>下标 <code>i</code> <strong>之后</strong>&nbsp;的 <code>k</code>&nbsp;个元素是 <strong>非递减的</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>按 <strong>升序</strong>&nbsp;返回所有好下标。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,1,1,1,3,4,1], k = 2\n",
    "<b>输出：</b>[2,3]\n",
    "<b>解释：</b>数组中有两个好下标：\n",
    "- 下标 2 。子数组 [2,1] 是非递增的，子数组 [1,3] 是非递减的。\n",
    "- 下标 3 。子数组 [1,1] 是非递增的，子数组 [3,4] 是非递减的。\n",
    "注意，下标 4 不是好下标，因为 [4,1] 不是非递减的。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,1,1,2], k = 2\n",
    "<b>输出：</b>[]\n",
    "<b>解释：</b>数组中没有好下标。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n / 2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-all-good-indices](https://leetcode.cn/problems/find-all-good-indices/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-all-good-indices](https://leetcode.cn/problems/find-all-good-indices/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,1,1,3,4,1]\\n2', '[2,1,1,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        if k == 1:\n",
    "            return [*range(1, len(nums)-1)]\n",
    "        # 寻找谷底\n",
    "        down = up = 1\n",
    "        ans = []\n",
    "        for i in range(1, len(nums) - k - 1):\n",
    "            if nums[i] <= nums[i-1]:\n",
    "                down += 1\n",
    "            else:\n",
    "                down = 1\n",
    "            if nums[i + k + 1] >= nums[i + k]:\n",
    "                up += 1\n",
    "            else:\n",
    "                up = 1\n",
    "            if up >= k and down >= k:\n",
    "                ans.append(i + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        if k == 1:\n",
    "            return [*range(1, len(nums) - 1)]\n",
    "        # 寻找谷底\n",
    "        down = up = 1\n",
    "        ans = []\n",
    "        for i in range(1, len(nums) - k - 1):\n",
    "            if nums[i] <= nums[i-1]:\n",
    "                down += 1\n",
    "            else:\n",
    "                down = 1\n",
    "            if nums[i + k + 1] >= nums[i + k]:\n",
    "                up += 1\n",
    "            else:\n",
    "                up = 1\n",
    "            if up >= k and down >= k:\n",
    "                ans.append(i + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n < 2*k + 1:\n",
    "            return []\n",
    "        if k == 1:\n",
    "            return list(range(1, n-1))\n",
    "        front, back, res = deque(), deque(), []\n",
    "        for i in range(k-2):\n",
    "            if nums[i] >= nums[i+1]:\n",
    "                front.append(i)\n",
    "            if nums[i+k+1] <= nums[i+k+2]:\n",
    "                back.append(i+k+1)\n",
    "        for i in range(k, n-k):\n",
    "            if nums[i-2] >= nums[i-1]:\n",
    "                front.append(i-2)\n",
    "            if nums[i+k-1] <= nums[i+k]:\n",
    "                back.append(i+k-1)\n",
    "            if len(front) == k-1 and len(back) == k-1:\n",
    "                res.append(i)\n",
    "            if front and front[0] == i-k:\n",
    "                front.popleft()\n",
    "            if back and back[0] == i+1:\n",
    "                back.popleft()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        '''\n",
    "        单调栈\n",
    "        两边各运行一次\n",
    "        '''\n",
    "        def f(nums):\n",
    "            stack = []\n",
    "            res = []\n",
    "            for i in range(len(nums)):\n",
    "                # print(i,nums[i],[nums[i] for i in stack])\n",
    "                if len(stack)>=k and stack[-k]==i-k:\n",
    "                    res.append(1)\n",
    "                else:\n",
    "                    res.append(0)\n",
    "                while stack and nums[stack[-1]]<nums[i]:\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "            return res\n",
    "        forward_cnt = f(nums)\n",
    "        backward_cnt = f(nums[::-1])[::-1]\n",
    "        # print(forward_cnt)\n",
    "        # print(backward_cnt)\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if forward_cnt[i] and backward_cnt[i]:\n",
    "                res.append(i)\n",
    "        return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        prefix, suffix = [False] * n, [False] * n\n",
    "        pre1, pre2, count1, count2 = inf, -inf, 0, 0\n",
    "        for i in range(n):\n",
    "            if nums[i] <= pre1:\n",
    "                count1 += 1\n",
    "            else:\n",
    "                count1 = 1\n",
    "            pre1 = nums[i]\n",
    "            if count1 >= k and i + 1 < n:\n",
    "                prefix[i + 1] = True\n",
    "            if nums[i] >= pre2:\n",
    "                count2 += 1\n",
    "            else:\n",
    "                count2 = 1\n",
    "            pre2 = nums[i]\n",
    "            if count2 >= k and i - k >= 0:\n",
    "                suffix[i - k] = True\n",
    "        \n",
    "        return [i for i in range(n) if prefix[i] and suffix[i]]\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        l = len(nums)\n",
    "        dp = [0 for i in range(l)]\n",
    "        c = 0\n",
    "        res = []\n",
    "        for i in range(1, l):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                c += 1\n",
    "                dp[i] = 0\n",
    "            elif nums[i] == nums[i - 1]:\n",
    "                c += 1\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "            else:\n",
    "                c = 0\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "            if c >= k - 1 and i - k - 1 >= 0 and dp[i - k - 1] >= k - 1:\n",
    "                res.append(i - k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        ht = dict()\n",
    "        n = len(nums)\n",
    "        cur_de = 1\n",
    "        cur_in = 1\n",
    "        res = []\n",
    "        if k == 1:\n",
    "            return [x for x in range(1, n-1)]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if nums[i] >= nums[i-1]:\n",
    "                cur_in += 1\n",
    "                if cur_in >= k and i-k in ht:\n",
    "                    res.append(i-k)\n",
    "                if nums[i] > nums[i-1]:\n",
    "                    cur_de = 1\n",
    "            if nums[i] <= nums[i-1]:\n",
    "                cur_de += 1\n",
    "                if cur_de >= k:\n",
    "                    ht[i+1] = 0\n",
    "                if nums[i] < nums[i-1]:\n",
    "                    cur_in = 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans=[]\n",
    "        n=len(nums)\n",
    "        #[1,1,1,1,2,3,3]\n",
    "        #[3,2,2,2,2,2,1]\n",
    "        pre=[1]*(n)\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                pre[i]=pre[i-1]+1\n",
    "            else:\n",
    "                pre[i]=pre[i-1]\n",
    "        suf=[1]*n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if nums[i]>nums[i+1]:\n",
    "                suf[i]=suf[i+1]+1\n",
    "            else:\n",
    "                suf[i]=suf[i+1]\n",
    "        print(pre)\n",
    "        print(suf)\n",
    "        for i in range(k,n-k,1):\n",
    "            if pre[i-k]==pre[i-1] and suf[i+1]==suf[i+k]:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        nonincreasing=[]\n",
    "        nondecreasing=[]\n",
    "        nileft,niright=0,0\n",
    "        ndleft,ndright=0,0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if i==n-1:\n",
    "                nonincreasing.append((nileft,i))\n",
    "            elif nums[i]<nums[i+1]:\n",
    "                nonincreasing.append((nileft,i))\n",
    "                nileft=i+1\n",
    "            if i==n-1:\n",
    "                nondecreasing.append((ndleft,i))\n",
    "            elif nums[i]>nums[i+1]:\n",
    "                nondecreasing.append((ndleft,i))\n",
    "                ndleft=i+1\n",
    "        # print(nonincreasing,nondecreasing)\n",
    "        nonincreasingk=[-1]*n\n",
    "        nondecreasingk=[-1]*n\n",
    "        for i in range(len(nonincreasing)):\n",
    "            for j in range(nonincreasing[i][0],nonincreasing[i][1]+1):\n",
    "                nonincreasingk[j]=i\n",
    "        for i in range(len(nondecreasing)):\n",
    "            for j in range(nondecreasing[i][0],nondecreasing[i][1]+1):\n",
    "                nondecreasingk[j]=i\n",
    "        # print(nonincreasingk,nondecreasingk)\n",
    "        res=[]\n",
    "        for i in range(k,n-k):\n",
    "            if nonincreasingk[i-1]==nonincreasingk[i-k] \\\n",
    "            and nondecreasingk[i+1]==nondecreasingk[i+k]:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        jian = [0] *n\n",
    "        zeng = [n-1] *n\n",
    "        res = []\n",
    "        for i in range(1,n):\n",
    "            jian[i] = i if nums[i] > nums[i-1] else jian[i-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            zeng[i] = i if nums[i] > nums[i+1] else zeng[i+1]\n",
    "        print(jian,zeng)\n",
    "        for i in range(k,n-k):\n",
    "            if jian[i-1] <= i-k and zeng[i+1] >= i+k:\n",
    "                res += [i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        jian = [0] *n\n",
    "        zeng = [n-1] *n\n",
    "        res = []\n",
    "        for i in range(1,n):\n",
    "            jian[i] = i if nums[i] > nums[i-1] else jian[i-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            zeng[i] = i if nums[i] > nums[i+1] else zeng[i+1]\n",
    "        print(jian,zeng)\n",
    "        for i in range(k,n-k):\n",
    "            if jian[i-1] <= i-k and zeng[i+1] >= i+k:\n",
    "                res += [i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        q = deque()\n",
    "        left = [False] * n\n",
    "        for i in range(n):\n",
    "            while q and nums[q[-1]] < nums[i]:\n",
    "                q.pop()\n",
    "            while q and q[0] + k <= i:\n",
    "                q.popleft()\n",
    "            q.append(i)\n",
    "            if len(q) == k:\n",
    "                left[i] = True\n",
    "        q.clear()\n",
    "        right = [False] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while q and nums[q[-1]] < nums[i]:\n",
    "                q.pop()\n",
    "            while q and i + k <= q[0]:\n",
    "                q.popleft()\n",
    "            q.append(i)\n",
    "            if len(q) == k:\n",
    "                right[i] = True\n",
    "        ans = []\n",
    "        for i in range(1, n - 1):\n",
    "            if left[i - 1] and right[i + 1]:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        l, r = k, n - k\n",
    "        d1 = deque()\n",
    "        d2 = deque()\n",
    "        for i in range(l - k, l) :\n",
    "            if not 0 <= i < n :\n",
    "                continue\n",
    "            while 0 <= i < n and d1 and nums[i] > d1[-1][0] :\n",
    "                d1.pop()\n",
    "            d1.append((nums[i], i))\n",
    "        for i in range(l + 1, l + k + 1) :\n",
    "            if not 0 <= i < n :\n",
    "                continue\n",
    "            while 0 <= i < n and d2 and nums[i] < d2[-1][0] :\n",
    "                d2.pop()\n",
    "            d2.append((nums[i], i))\n",
    "        if len(d1) == k and len(d2) == k :\n",
    "            res.append(l)\n",
    "        for i in range(l + 1, r) :\n",
    "            while d1 and nums[i - 1] > d1[-1][0] :\n",
    "                d1.pop()\n",
    "            while d2 and nums[i + k] < d2[-1][0] :\n",
    "                d2.pop()\n",
    "            while d1 and d1[0][1] < i - k :\n",
    "                d1.popleft()\n",
    "            while d2 and d2[0][1] <= i :\n",
    "                d2.popleft()\n",
    "            d1.append((nums[i - 1], i - 1))\n",
    "            d2.append((nums[i + k], i + k))\n",
    "            if len(d1) == k and len(d2) == k :\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if 2 * k + 1 > n: return []\n",
    "        left = [False] * n\n",
    "        right = [False] * n\n",
    "        stk = []\n",
    "        for i, x in enumerate(nums):\n",
    "            if stk and len(stk) >= k:\n",
    "                left[i] = True\n",
    "            if stk and x > stk[-1]:\n",
    "                stk.clear()\n",
    "            stk.append(x)\n",
    "        stk = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            x = nums[i]\n",
    "            if stk and len(stk) >= k:\n",
    "                right[i] = True\n",
    "            if stk and x > stk[-1]:\n",
    "                stk.clear()\n",
    "            stk.append(x)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if left[i] and right[i]:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf_ins = [1] * n\n",
    "        cnt = 1\n",
    "        if k == 1:return [x for x in range(1, n - 1)]\n",
    "        for i in range(n - 3, 0, -1):\n",
    "            if nums[i + 1] <= nums[i + 2]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt = 1\n",
    "            suf_ins[i] = cnt\n",
    "        ans = []\n",
    "        cnt = 1\n",
    "        for i in range(2, n - 2):\n",
    "            if nums[i - 1] <= nums[i - 2]:\n",
    "                cnt += 1\n",
    "                if suf_ins[i] >= k and cnt >= k:\n",
    "                    ans.append(i)\n",
    "            else:cnt = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        if(n-k<=k):\n",
    "            return res\n",
    "        if(k==1):\n",
    "            for i in range(1,n-1):\n",
    "                res.append(i)\n",
    "            return res\n",
    "        pre = [1] * n\n",
    "        suf = 1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                pre[i]+=pre[i-1]\n",
    "            if nums[i]>=nums[i-1]:\n",
    "                suf += 1\n",
    "            else:\n",
    "                suf = 1\n",
    "            if i-k >= k and pre[i-1-k]>=k and suf>=k:\n",
    "                res.append(i-k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        l = len(nums)\n",
    "        if l < 2 * k + 1:\n",
    "            return []\n",
    "        if k == 1:\n",
    "            return [i for i in range(1, l - 1)]\n",
    "\n",
    "        R = 0\n",
    "        F = 0\n",
    "        rise = [0 for i in range(l + 1)]\n",
    "        fall = [0 for i in range(l + 1)]\n",
    "        ans = []\n",
    "        tmp = nums[0]\n",
    "        for i in range(l):\n",
    "            if nums[i] == tmp:\n",
    "                R += 1\n",
    "                F += 1\n",
    "            elif nums[i] > tmp:\n",
    "                    R += 1\n",
    "                    F = 1\n",
    "            elif nums[i] < tmp:\n",
    "                    R = 1\n",
    "                    F += 1\n",
    "            tmp = nums[i]\n",
    "            if F >= k:\n",
    "                fall[i + 1] = F\n",
    "            if R >= k and i - k >= 0:\n",
    "                if fall[i - k] >= k:\n",
    "                    ans.append(i - k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        l = len(nums)\n",
    "        if l < 2 * k + 1:\n",
    "            return []\n",
    "        if k == 1:\n",
    "            return [i for i in range(1, l - 1)]\n",
    "\n",
    "        R = 0\n",
    "        F = 0\n",
    "        rise = [0 for i in range(l + 1)]\n",
    "        fall = [0 for i in range(l + 1)]\n",
    "        ans = []\n",
    "        tmp = nums[0]\n",
    "        for i in range(l):\n",
    "            if nums[i] == tmp:\n",
    "                R += 1\n",
    "                F += 1\n",
    "            elif nums[i] > tmp:\n",
    "                    R += 1\n",
    "                    F = 1\n",
    "            elif nums[i] < tmp:\n",
    "                    R = 1\n",
    "                    F += 1\n",
    "            tmp = nums[i]\n",
    "            if F >= k:\n",
    "                fall[i + 1] = F\n",
    "            if R >= k and i - k >= 0:\n",
    "                if fall[i - k] >= k:\n",
    "                    ans.append(i - k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if k == 1:\n",
    "            return [m for m in range(k, n-k)]\n",
    "        notIncrease = [1] * n\n",
    "        notDecrease = [1] * n\n",
    "        notIncrease[0] = 0\n",
    "        notDecrease[-1] = 0\n",
    "        for i in range(2, n):\n",
    "            if nums[i-1] <= nums[i-2]:\n",
    "                notIncrease[i] = notIncrease[i-1] + 1\n",
    "        for j in range(n-3, -1, -1):\n",
    "            if nums[j+1] <= nums[j+2]:\n",
    "                notDecrease[j] = notDecrease[j+1] + 1\n",
    "        res = []\n",
    "        for m in range(k, n-k):\n",
    "            if notIncrease[m] >= k and notDecrease[m] >= k:\n",
    "                res.append(m)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        prefix, suffix = [False] * n, [False] * n\n",
    "        pre1, pre2, count1, count2 = inf, -inf, 0, 0\n",
    "        for i in range(n):\n",
    "            if nums[i] <= pre1:\n",
    "                count1 += 1\n",
    "            else:\n",
    "                count1 = 1\n",
    "            pre1 = nums[i]\n",
    "            if count1 >= k and i + 1 < n:\n",
    "                prefix[i + 1] = True\n",
    "            print(count1, i)\n",
    "            if nums[i] >= pre2:\n",
    "                count2 += 1\n",
    "            else:\n",
    "                count2 = 1\n",
    "            pre2 = nums[i]\n",
    "            if count2 >= k and i - k >= 0:\n",
    "                suffix[i - k] = True\n",
    "\n",
    "        print(prefix, suffix)\n",
    "        \n",
    "        return [i for i in range(n) if prefix[i] and suffix[i]]\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        if k==1:\n",
    "            return [i for i in range(1,len(nums)-1)]\n",
    "        dp1 = [1 for i in range(len(nums))]\n",
    "        dp2 = [1 for i in range(len(nums))]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                dp1[i] = dp1[i-1]+1\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            if nums[i]<=nums[i+1]:\n",
    "                dp2[i] = dp2[i+1]+1\n",
    "        res = []\n",
    "        for i in range(k,len(nums)-k):\n",
    "            if dp1[i-1]>=k and dp2[i+1]>=k:\n",
    "                res.append(i)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        if 2 * k + 1 > len(nums):\n",
    "            return []\n",
    "        if k == 1:\n",
    "            return list(range(1, len(nums)-1, 1))\n",
    "   \n",
    "        dp_left, dp_right = [1] * len(nums), [1] * len(nums)\n",
    "        for i in range(1, len(nums), 1):\n",
    "            dp_left[i] = dp_left[i-1] + 1 if nums[i] <= nums[i-1] else 1\n",
    "        for j in range(len(nums)-2, -1, -1):\n",
    "            dp_right[j] = dp_right[j+1] + 1 if nums[j] <= nums[j+1] else 1\n",
    "\n",
    "        ans = []\n",
    "        for nk in range(k, len(nums)-k, 1):\n",
    "            if dp_left[nk-1] >= k and dp_right[nk+1] >= k:\n",
    "                ans.append(nk)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        sk=[0]\n",
    "        n=len(nums)\n",
    "        sr=[n-1]\n",
    "        pr=nums[0]\n",
    "        for i in range(1,n):\n",
    "            x=nums[i]\n",
    "            if x<=pr:\n",
    "              sk.append(sk[-1])\n",
    "            else:\n",
    "              sk.append(i)\n",
    "            pr=x\n",
    "        pr=nums[-1]    \n",
    "        for i in range(n-2,-1,-1):\n",
    "           x=nums[i]\n",
    "           if x<=pr:\n",
    "             sr.append(sr[-1])\n",
    "           else:\n",
    "             sr.append(i)\n",
    "           pr=x  \n",
    "        sr=sr[::-1]\n",
    "        ans=[]\n",
    "        print(sk)\n",
    "        print(sr)\n",
    "        for i in range(1,n-1):\n",
    "          # print(i)\n",
    "          # print(i-1,sk[i-1])\n",
    "          # print(i+1,sr[i+1])\n",
    "          if i-1-sk[i-1]+1>=k and sr[i+1]-i>=k:\n",
    "            \n",
    "            ans.append(i)       \n",
    "        return ans             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        a = nums\n",
    "        ldp = [1] *len(a)\n",
    "        rdp = [1] * len(a)\n",
    "        dp = [1] * len(a)\n",
    "        res = []\n",
    "        for i in range(1,len(a)):\n",
    "            if a[i] <= a[i-1]:\n",
    "                ldp[i] = min(ldp[i-1]+1,k)\n",
    "\n",
    "        for i in range(len(a)-1,0,-1):\n",
    "            if a[i] >= a[i-1]:\n",
    "                rdp[i-1] = min(rdp[i]+1,k)\n",
    "\n",
    "        for i in range(1,len(a)-1):\n",
    "            dp[i] = ldp[i-1] + rdp[i+1] +1\n",
    "\n",
    "\n",
    "\n",
    "        # print(ldp)\n",
    "        # print(rdp)\n",
    "        # print(dp)\n",
    "        s = 0\n",
    "        for i in range(len(dp)):\n",
    "            if dp[i] == 2*k+1:\n",
    "                res.append(i)\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        dec = [1]*n\n",
    "        for i in range(n-2,k,-1):\n",
    "            if nums[i] <= nums[i+1]:\n",
    "                dec[i] = dec[i+1]+1\n",
    "        inc = 1\n",
    "        for i in range(1,n-k):\n",
    "            if inc >= k and dec[i+1] >= k:\n",
    "                ans.append(i)\n",
    "            if nums[i-1] >= nums[i]:\n",
    "                inc += 1\n",
    "            else:\n",
    "                inc = 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        dec = [1] * n \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] <= nums[i + 1]:\n",
    "                dec[i] = dec[i + 1] + 1\n",
    "        \n",
    "        inc = 1 # 代表当前非递增子串的最长多长\n",
    "        for i in range(1, n - k):\n",
    "            # 因为i下标之前有i个数字，所有直接用inc，但是dec[i]代表的包括i下标及其之后的有多少非递减的。\n",
    "            # 所以这里用dec[i+1]\n",
    "            if inc >= k and dec[i + 1] >= k:\n",
    "                ans.append(i)\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                inc += 1\n",
    "            else:\n",
    "                inc = 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        # n = len(nums)\n",
    "        # if n < 2*k + 1:\n",
    "        #     return []\n",
    "        # if k == 1:\n",
    "        #     return list(range(1, n-1))\n",
    "        # front, back, res = deque(), deque(), []\n",
    "        # for i in range(k-2):\n",
    "        #     if nums[i] >= nums[i+1]:\n",
    "        #         front.append(i)\n",
    "        #     if nums[i+k+1] <= nums[i+k+2]:\n",
    "        #         back.append(i+k+1)\n",
    "        # for i in range(k, n-k):\n",
    "        #     if nums[i-2] >= nums[i-1]:\n",
    "        #         front.append(i-2)\n",
    "        #     if nums[i+k-1] <= nums[i+k]:\n",
    "        #         back.append(i+k-1)\n",
    "        #     if len(front) == k-1 and len(back) == k-1:\n",
    "        #         res.append(i)\n",
    "        #     if front and front[0] == i-k:\n",
    "        #         front.popleft()\n",
    "        #     if back and back[0] == i+1:\n",
    "        #         back.popleft()\n",
    "        # return res\n",
    "\n",
    "        # --------------------------------\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        back = [1] * n \n",
    "        for i in range(n-2, k, -1):\n",
    "            if nums[i] <= nums[i+1]:\n",
    "                back[i] = back[i+1] + 1\n",
    "        front = 1\n",
    "        for i in range(1, n-k):\n",
    "            if front >= k and back[i+1] >= k:\n",
    "                res.append(i)\n",
    "            if nums[i-1] >= nums[i]:\n",
    "                front += 1\n",
    "            else:\n",
    "                front = 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ret = []\n",
    "        if n < 2 * k + 1: return ret\n",
    "        for i in range(k, n - k):\n",
    "            if nums[i-k:i] == list(sorted(nums[i-k:i], reverse=True)) and nums[i+1:i+k+1] == list(sorted(nums[i+1:i+k+1])):\n",
    "                ret.append(i)\n",
    "        ret.sort()\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ret = []\n",
    "        dec = [1] * n\n",
    "        for i in range(n-2, k, -1):\n",
    "            if nums[i] <= nums[i+1]:\n",
    "                dec[i] = dec[i+1] + 1\n",
    "        inc = 1\n",
    "        for i in range(1, n-k):\n",
    "            if inc >= k and dec[i+1] >= k:\n",
    "                ret.append(i)\n",
    "            if nums[i-1] >= nums[i]:\n",
    "                inc += 1\n",
    "            else:\n",
    "                inc = 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        right = [0]*(n+1)\n",
    "        left = [0]*(n+1)\n",
    "        for i in range(1,n) :\n",
    "            if(nums[i] <= nums[i-1]) :\n",
    "                left[i] = left[i-1] +1\n",
    "            else :\n",
    "                left[i] = 0 \n",
    "        for i in range(n-2,0,-1):\n",
    "            if nums[i] <= nums[i+1] :\n",
    "                right[i] =right[i+1] + 1\n",
    "            else :\n",
    "                right[i] =0\n",
    "        ans = []\n",
    "        for i  in range(1,n-1) :\n",
    "            if left[i-1] >=k-1  and right[i+1] >=k-1 :\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "class Solution:\r\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\r\n",
    "        n = len(nums)\r\n",
    "        ans = []\r\n",
    "        dec = [1] * n\r\n",
    "        for i in range(n - 2, k, -1):\r\n",
    "            if nums[i] <= nums[i + 1]:\r\n",
    "                dec[i] = dec[i + 1] + 1  # 递推\r\n",
    "        inc = 1\r\n",
    "        for i in range(1, n - k):\r\n",
    "            if inc >= k and dec[i + 1] >= k:\r\n",
    "                ans.append(i)\r\n",
    "            if nums[i - 1] >= nums[i]:\r\n",
    "                inc += 1  # 递推\r\n",
    "            else:\r\n",
    "                inc = 1\r\n",
    "        return ans\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dec = [0] * n\n",
    "\n",
    "        dec[n - 1] = 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            dec[i] = (dec[i + 1] + 1) if nums[i] <= nums[i + 1] else 1\n",
    "        \n",
    "        inc = [0] * n\n",
    "        inc[0] = 1\n",
    "        for i in range(1, n):\n",
    "            inc[i] = (inc[i - 1] + 1) if nums[i] <= nums[i - 1] else 1\n",
    "        \n",
    "        ans = []\n",
    "        # print(inc)\n",
    "        # print(dec)\n",
    "        for i in range(k, n - k):\n",
    "            if inc[i - 1] >= k and dec[i + 1] >= k:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dec = [1] * n\n",
    "        inc = [1] * n\n",
    "        for i in range(1, n):\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                inc[i] = inc[i - 1] + 1\n",
    "        \n",
    "        for i in range(n - 2, 0, -1):\n",
    "            if nums[i] <= nums[i + 1]:\n",
    "                dec[i] = dec[i + 1] + 1\n",
    "        \n",
    "        res = []\n",
    "        for i in range(k, n - k):\n",
    "            if inc[i - 1] >= k and dec[i + 1] >= k: \n",
    "                res.append(i)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        increase = [1]*n\n",
    "        decrease = [1]*n\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                decrease[i] = decrease[i-1] + 1\n",
    "\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if nums[i]<=nums[i+1]:\n",
    "                increase[i] = increase[i+1] + 1 \n",
    "        # print(increase)\n",
    "        # print(decrease)\n",
    "        rs = []\n",
    "        for i in range(k,n-k):\n",
    "            if decrease[i-1]>=k and increase[i+1]>=k:\n",
    "                rs.append(i)\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans=[]\n",
    "        n=len(nums)\n",
    "        cur=0\n",
    "        l=set()\n",
    "        if k==1:\n",
    "            return list(range(1,n-1))\n",
    "        cur=0\n",
    "        for i in range(n-1,0,-1):\n",
    "            if nums[i]-nums[i-1]>=0:\n",
    "                cur+=1\n",
    "                if cur>=k-1 :\n",
    "                    l.add(i-2)\n",
    "            else:\n",
    "                cur=0\n",
    "        cur=0\n",
    "        for i in range(n-1):\n",
    "            if nums[i+1]-nums[i]<=0:\n",
    "                cur+=1\n",
    "                if cur>=k-1 and i+2 in l:\n",
    "                    ans.append(i+2)\n",
    "            else:\n",
    "                cur=0\n",
    "\n",
    "        \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        l,r = [1]*n, [1]*n\n",
    "        for i in range(1, n):\n",
    "            l[i] = l[i-1]+1 if nums[i]<=nums[i-1] else 1\n",
    "            r[i] = r[i-1]+1 if nums[i]>=nums[i-1] else 1\n",
    "        ans = []\n",
    "        print(l)\n",
    "        print(r)\n",
    "        for i in range(k,n-k):\n",
    "            if l[i-1]>=k and r[i+k]>=k:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        pre=[0]*len(nums)\n",
    "        back=[0]*len(nums)\n",
    "        pre[0]=1\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                pre[i]=pre[i-1]+1\n",
    "            else:\n",
    "                pre[i]=1\n",
    "        back[-1]=1\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            if nums[i]<=nums[i+1]:\n",
    "                back[i]=back[i+1]+1\n",
    "            else:\n",
    "                back[i]=1\n",
    "        ans=[]\n",
    "        print(pre)\n",
    "        print(back)\n",
    "        for i in range(1,len(nums)-1):\n",
    "            if pre[i-1]>=k and back[i+1]>=k:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        suf = [1] * n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if nums[i] <= nums[i+1]:\n",
    "                suf[i] = suf[i+1] + 1\n",
    "        ans = []\n",
    "        pre = 1\n",
    "        print(suf)\n",
    "        for i in range(1, n-k):\n",
    "            if pre >= k and suf[i+1] >= k:\n",
    "                ans.append(i)\n",
    "            if nums[i] <= nums[i-1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n < 2 * k +1:\n",
    "            return []\n",
    "\n",
    "        '''\n",
    "        after[i] 表示i后面最长 非递减的个数\n",
    "        befor[i] 表示i前面最长 非递增的个数\n",
    "        倒序遍历，如果当前值小于等于后一个，当前值 +1 else 1\n",
    "        正序遍历，如果当前值小于等于前一个，当前值 +1 slse 1\n",
    "        '''\n",
    "        after = [1] * n \n",
    "        befor = [1] * n \n",
    "        for i in range(n-2,k-1,-1):\n",
    "            if nums[i] <=  nums[i+1]:\n",
    "                after[i-1] += after[i] \n",
    "        ans = []\n",
    "        for j in range(1,n-k):\n",
    "            if nums[j] <=  nums[j-1]:\n",
    "                befor[j+1] += befor[j]\n",
    "            \n",
    "            if j >= k :\n",
    "                print (j)\n",
    "                if after[j] >= k and befor[j] >= k :\n",
    "\n",
    "                    ans.append(j)\n",
    "        print (befor,after)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        front = [1]\n",
    "        end = [1]\n",
    "        ft = 1\n",
    "        ed = 1\n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i+1] <= nums[i]:\n",
    "                ft += 1\n",
    "                front.append(ft)\n",
    "            else:\n",
    "                ft = 1\n",
    "                front.append(1)\n",
    "\n",
    "            if nums[i+1] >= nums[i]:\n",
    "                ed += 1\n",
    "                end.append(ed)\n",
    "            else:\n",
    "                ed = 1\n",
    "                end.append(1)\n",
    "        \n",
    "        res = []\n",
    "        for i in range(k, len(nums) - k):\n",
    "            if front[i-1] >= k and end[i+k] >= k:\n",
    "                res.append(i)\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, a: List[int], t: int) -> List[int]:\n",
    "        n=len(a)\n",
    "        l,r=[i for i in range(n)],[i for i in range(n)]\n",
    "        i=0\n",
    "        while i<n:\n",
    "            j=i+1\n",
    "            while j<n and a[j]<=a[j-1]:\n",
    "                j+=1\n",
    "            for k in range(i,j):\n",
    "                l[k]=i\n",
    "            i=j\n",
    "        i=0\n",
    "        while i<n:\n",
    "            j=i+1\n",
    "            while j<n and a[j]>=a[j-1]:\n",
    "                j+=1\n",
    "            for k in range(i,j):\n",
    "                r[k]=j-1\n",
    "            i=j\n",
    "        ans=[]\n",
    "        for i in range(t,n-t):\n",
    "            if l[i-1]<=i-t and r[i+1]>=i+t:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        dp = [[0, 0] for i in range(len(nums))] # dp[i][0]: 前k个非递增，dp[i][1]前k个非递减\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] <= nums[i-1]:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "            else:\n",
    "                dp[i][0] = i\n",
    "            if nums[i] >= nums[i-1]:\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "            else:\n",
    "                dp[i][1] = i\n",
    "        res = []\n",
    "        for i in range(k, len(nums)-k):\n",
    "            if i - dp[i-1][0] >=k and i + k -dp[i+k][1] + 1 >=k:\n",
    "                res.append(i)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        if n-k==k:\n",
    "            return res\n",
    "\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        \n",
    "        for i,c in enumerate(nums):\n",
    "            while stack1 and (i-1>=0 and nums[stack1[-1]]<nums[i-1]):\n",
    "                stack1.pop()\n",
    "            \n",
    "            if i-1>=0:\n",
    "                stack1.append(i-1)\n",
    "                \n",
    "            while stack2 and (i+k<n and nums[stack2[-1]]>nums[i+k]):\n",
    "                stack2.pop()\n",
    "                \n",
    "            if i+k<n:\n",
    "                stack2.append(i+k)\n",
    "            if len(stack1)>=k and len(stack2)>=k and stack1[-k] == i-k and stack2[-k] == i+1:\n",
    "                res.append(i)\n",
    "                \n",
    "        return res\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        # def check(i,k):\n",
    "        #     flag = True\n",
    "        #     for j in range(k-1):\n",
    "        #         flag &= (nums[i-j-1]-nums[i-2-j]<=0) and (nums[i+j+2]-nums[i+j+1]>=0)\n",
    "        #         if not flag:\n",
    "        #             break\n",
    "        #     return flag\n",
    "        # res = []\n",
    "        # for i in range(k,n-k):\n",
    "        #     if check(i,k):\n",
    "        #         res.append(i)\n",
    "        # return res\n",
    "        dp1 = [1] * n\n",
    "        dp2 = [1] * n\n",
    "        res = []\n",
    "        for i in range(1,n):\n",
    "            if nums[i] <= nums[i-1]:\n",
    "                dp1[i] = dp1[i-1] + 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if nums[i] <= nums[i+1]:\n",
    "                dp2[i] = dp2[i+1] + 1\n",
    "        for i in range(k, n-k):\n",
    "            if dp1[i-1]>=k and dp2[i+1]>=k:\n",
    "                res.append(i)\n",
    "        print(dp1,dp2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        dec = [1 for i in range(n)]\n",
    "        inc = [1 for i in range(n)]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] <= nums[i + 1]:\n",
    "                dec[i] = dec[i + 1] + 1\n",
    "            else:\n",
    "                pass\n",
    "        for i in range(1, n - k):\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                inc[i] = inc[i - 1] + 1\n",
    "            if i >= k:\n",
    "                if inc[i - 1] >= k and dec[i + 1] >= k:\n",
    "                    res.append(i)\n",
    "        print(inc, dec)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        st1 , st2 = [] , []\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        for i , num in enumerate(nums):\n",
    "            while st1 and nums[i-1] > nums[st1[-1]]:\n",
    "                st1.pop()\n",
    "            if i-1>=0:\n",
    "                st1.append(i-1)\n",
    "            while st2 and (i + k < n and nums[i+k] < nums[st2[-1]]):\n",
    "                st2.pop()\n",
    "            if i+k<n:\n",
    "                st2.append(i+k)\n",
    "            if len(st1)>=k and len(st2)>=k and st1[-k] == i-k and st2[-k] == i+1:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        pre=nums[0]\n",
    "        left=[True]\n",
    "        right=[True]\n",
    "        n=len(nums)\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]<=pre:\n",
    "                left.append(True)\n",
    "            else:\n",
    "                left.append(False)\n",
    "            pre=nums[i]\n",
    "        pre=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>=pre:\n",
    "                right.append(True)\n",
    "            else:\n",
    "                right.append(False)\n",
    "            pre=nums[i]\n",
    "        \n",
    "        \n",
    "        l_prefix=[]\n",
    "        r_prefix=[]\n",
    "        s=0\n",
    "        for i in left:\n",
    "            if i==True:\n",
    "                s+=1\n",
    "            l_prefix.append(s)\n",
    "        s=0\n",
    "        for i in right:\n",
    "            if i==True:\n",
    "                s+=1\n",
    "            r_prefix.append(s)\n",
    "        # print(left,right)\n",
    "        # print(l_prefix,r_prefix)\n",
    "        res=[]\n",
    "        for i in range(k,n-k):\n",
    "            if l_prefix[i-1]-l_prefix[i-k]==k-1 and r_prefix[i+k]-r_prefix[i+1]==k-1:\n",
    "                res.append(i)\n",
    "            # print(l_prefix[i-1]-l_prefix[i-k])\n",
    "            # print(r_prefix[i+k]-r_prefix[i+1])\n",
    "        return res\n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left = []\n",
    "        stack = []\n",
    "        for num in nums:\n",
    "            left.append(len(stack))\n",
    "            if stack and stack[-1] < num:\n",
    "                stack = []\n",
    "            stack.append(num)\n",
    "        right = [0] * n\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            right[i] = len(stack)\n",
    "            num = nums[i]\n",
    "            if stack and stack[-1] < num:\n",
    "                stack = []\n",
    "            stack.append(num)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if left[i] >= k and right[i] >= k:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        n = len(nums)\n",
    "        f = [0] * n\n",
    "        b = [0] * n\n",
    "        \n",
    "        f = [0] * n #判断[i - 1, i]是否递增\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                f[i] = 1\n",
    "            elif nums[i] < nums[i - 1]:\n",
    "                f[i] = -1\n",
    "        \n",
    "        pf = [0] * (n + 1)\n",
    "        bf = [0] * (n + 1)\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            # 到第i个元素位置，非递增的区间数\n",
    "            if i == 1:\n",
    "                pf[i] = 0\n",
    "                continue\n",
    "            pf[i] = pf[i - 1] + (1 if f[i - 1] <= 0 else 0)\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            # 到第i个元素位置，非递减的区间数\n",
    "            if i == 1:\n",
    "                bf[i] = 0\n",
    "                continue\n",
    "            bf[i] = bf[i - 1] + (1 if f[i - 1] >= 0 else 0)\n",
    "\n",
    "        def query(q, l, r):\n",
    "            return q[r + 1] - q[l]\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        for i in range(k, n - k):\n",
    "            lc = query(pf, i - k + 1, i - 1)\n",
    "            rc = query(bf, i + 2, i + k)\n",
    "            print(i, lc, rc)\n",
    "            if lc == rc == k - 1:\n",
    "                res.append(i)\n",
    "        return res\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        stack1 = []         # 非递增（元素下标）\n",
    "        stack2 = []         # 非递减（元素下标）\n",
    "        \n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        for i, num in enumerate(nums):\n",
    "            \n",
    "            # nums[i-1]加入stack1？\n",
    "            while stack1 and nums[i-1] > nums[stack1[-1]]:\n",
    "                stack1.pop()\n",
    "            \n",
    "            if i-1 >= 0:\n",
    "                stack1.append(i-1)\n",
    "            \n",
    "            # nums[i+k]加入stack2？\n",
    "            while stack2 and (i+k < n and nums[i+k] < nums[stack2[-1]]):\n",
    "                stack2.pop()\n",
    "                \n",
    "            if i+k < n:\n",
    "                stack2.append(i+k)\n",
    "            \n",
    "            # nums[i]的前k个元素非递增，后k个元素非递减？\n",
    "            if len(stack1) >= k and len(stack2) >= k and stack1[-k] == i-k and stack2[-k] == i+1:\n",
    "                res.append(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        for i, num in enumerate(nums):\n",
    "            while stack1 and i - 1 >= 0 and nums[i - 1] > nums[stack1[-1]]:\n",
    "                stack1.pop()\n",
    "            if i - 1 >= 0:\n",
    "                stack1.append(i - 1)\n",
    "            while stack2 and i + k < n and nums[i + k] < nums[stack2[-1]]:\n",
    "                stack2.pop()\n",
    "            if i + k < n:\n",
    "                stack2.append(i + k)\n",
    "            if len(stack1) >= k and len(stack2) >= k and \\\n",
    "                    stack1[-k] == i - k and stack2[-k] == i + 1:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 左边递减栈, 右边递增\n",
    "        left = []\n",
    "        st = []\n",
    "        for i, v in enumerate(nums):\n",
    "            if not st:\n",
    "                st.append(v)\n",
    "            else:\n",
    "                if st[-1] >= v:\n",
    "                    st.append(v)\n",
    "                else:\n",
    "                    st = []\n",
    "                    st.append(v)\n",
    "            left.append(len(st))\n",
    "\n",
    "        right = deque()\n",
    "        st = []\n",
    "        for v in nums[::-1]:\n",
    "            if not st:\n",
    "                st.append(v)\n",
    "            else:\n",
    "                if st[-1] >= v:\n",
    "                    st.append(v)\n",
    "                else:\n",
    "                    st = []\n",
    "                    st.append(v)\n",
    "            right.appendleft(len(st))\n",
    "\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        right = list(right)\n",
    "        for i in range(k, n - k):\n",
    "            if left[i - 1] >= k and right[i + 1] >= k:\n",
    "                ans.append(i)\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        # print(nums)\n",
    "        n = len(nums)\n",
    "        \n",
    "        def h1(nums):\n",
    "            # 非递减长度\n",
    "            res = [1]*n\n",
    "            for i in range(1, n):\n",
    "                if nums[i] <= nums[i-1]:\n",
    "                    res[i] = res[i-1] + 1\n",
    "            return res\n",
    "        a = h1(nums)\n",
    "        b = h1(nums[::-1])[::-1]\n",
    "        res = []\n",
    "        for i in range(1,n-1):\n",
    "            if a[i-1] >= k and b[i+1] >= k:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        def helper(nums):\n",
    "            n = len(nums)\n",
    "            res = [0]\n",
    "            cnt = 1\n",
    "            for i in range(1, n):\n",
    "                res.append(cnt)\n",
    "                if nums[i - 1] >= nums[i]:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cnt = 1\n",
    "            return res\n",
    "        \n",
    "        res1, res2 = helper(nums), helper(nums[::-1])[::-1]\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if res1[i] >= k and res2[i] >= k:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        A = [0] * n \n",
    "        B = [0] * n \n",
    "        A[0] = 1\n",
    "        B[n-1] = 1\n",
    "        for i in range(1, n):\n",
    "            if nums[i-1] >= nums[i]:\n",
    "                A[i] = A[i-1]+1\n",
    "            else:\n",
    "                A[i] = 1\n",
    "            if nums[n-i-1] <= nums[n-i]:\n",
    "                B[n-i-1] = B[n-i] + 1\n",
    "            else:\n",
    "                B[n-i-1] = 1\n",
    "        ans = []\n",
    "        # print(A,B)\n",
    "        for i in range(k, n-k):\n",
    "            if A[i-1] >= k and B[i+1] >= k:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        \n",
    "        if k==1:return list(range(1,n-1))\n",
    "        # if k==n/2:return []\n",
    "        d=[0]*n\n",
    "        p=[0]*n \n",
    "        for i in range(n-2,-1,-1):\n",
    "            if nums[i]<=nums[i+1]:\n",
    "                p[i]=p[i+1]+1\n",
    "\n",
    "        ans=[]\n",
    "        for i in range(1,n):\n",
    "            if k<=i<n-k and d[i-1]>=k-1 and p[i+1]>=k-1:\n",
    "                ans.append(i)\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                d[i]=d[i-1]+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if k > 1:\n",
    "            left = [1] * n\n",
    "            right = [1] * n\n",
    "\n",
    "            for i in range(1, n):\n",
    "                left[i] = left[i - 1] + 1 if nums[i] <= nums[i - 1] else 1\n",
    "                right[n - i - 1] = right[n - i] + 1 if nums[n - i - 1] <= nums[n - i] else 1\n",
    "\n",
    "            return [i for i in range(k, n - k) if left[i - 1] >= k and right[i + 1] >= k]\n",
    "        else:\n",
    "            return list(range(1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: list[int], k: int) -> list[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        def f(nums):\n",
    "            ans = list()\n",
    "            st = deque()\n",
    "            for i, num in enumerate(nums):\n",
    "                while st and num > st[-1]:\n",
    "                    st.clear()\n",
    "                st.append(num)\n",
    "                if len(st) == k:\n",
    "                    if n - i - 1 >= k + 1:\n",
    "                        ans.append(i + 1)\n",
    "                    st.popleft()\n",
    "            return ans\n",
    "\n",
    "        res = f(nums)\n",
    "        inv = set(f(nums[::-1]))\n",
    "        print(res)\n",
    "        print(inv)\n",
    "        k = 0\n",
    "        for i in res:\n",
    "            if n - 1 - i in inv:\n",
    "                res[k] = i\n",
    "                k += 1\n",
    "\n",
    "        return res[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        validright, validleft = collections.deque([]), collections.deque([])\n",
    "        validleft.append(0)\n",
    "        validl, validr = [0], [0]\n",
    "        for i in range(1, len(nums)):\n",
    "            if i > k-1 and validleft and validleft[0] <= i-k: validl.append(1)\n",
    "            else: validl.append(0)\n",
    "            if validleft and nums[i] > nums[validleft[-1]]:validleft = []\n",
    "            validleft.append(i)\n",
    "            # print(validleft)\n",
    "        # print(validl)\n",
    "        nums = nums[::-1]\n",
    "        validright.append(0)\n",
    "        for i in range(1, len(nums)):\n",
    "            if i > k-1 and validright and validright[0] <= i-k: validr.append(1)\n",
    "            else: validr.append(0)\n",
    "            if validright and nums[i] > nums[validright[-1]]:validright=[]\n",
    "            validright.append(i)\n",
    "        validr = validr[::-1]\n",
    "        # print(validr)\n",
    "        res = []\n",
    "        for i in range(len(validl)):\n",
    "            if validl[i] and validr[i]: res.append(i)\n",
    "        return res\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        answer_list = list()\n",
    "        nums_length = len(nums)\n",
    "        non_increasing_list = [1] * nums_length\n",
    "        non_decreasing_list = [1] * nums_length\n",
    "        for index in range(1, nums_length):\n",
    "            if nums[index] <= nums[index - 1]:\n",
    "                non_decreasing_list[index] = non_decreasing_list[index - 1] + 1\n",
    "        for index in range(nums_length - 2, -1, -1):\n",
    "            if nums[index] <= nums[index + 1]:\n",
    "                non_increasing_list[index] = non_increasing_list[index + 1] + 1\n",
    "        for index in range(k, nums_length - k):\n",
    "            if non_decreasing_list[index - 1] >= k and non_increasing_list[index + 1] >= k:\n",
    "                answer_list.append(index)\n",
    "        return answer_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left = [1] * n\n",
    "        right = [1] * n\n",
    "        for i in range(1, n):\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            if nums[n - i - 1] <= nums[n - i]:\n",
    "                right[n - i - 1] = right[n - i] + 1\n",
    "        return [i for i in range(k, n - k) if left[i - 1] >= k and right[i + 1] >= k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left = [1] * n\n",
    "        right = [1] * n\n",
    "        for i in range(1, n):\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            if nums[n - i - 1] <= nums[n - i]:\n",
    "                right[n - i - 1] = right[n - i] + 1\n",
    "        return [i for i in range(k, n - k) if left[i - 1] >= k and right[i + 1] >= k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        lens = len(nums)\n",
    "        left = [1] * lens\n",
    "        right = [1] * lens\n",
    "\n",
    "        for i in range(lens-1):\n",
    "            if nums[i] >= nums[i+1]:\n",
    "                left[i+1] = left[i]+1\n",
    "            if nums[lens - 1 - i] >= nums[lens - 2 - i]:\n",
    "                right[lens -2 -i] = right[lens -1 -i]+1\n",
    "        \n",
    "\n",
    "        return [i for i in range(k,lens-k) if left[i-1] >=k and right[i+1] >=k ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 前后缀分解\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "\n",
    "        pre = [1] * (len(nums) + 1)\n",
    "        suf = [1] * (len(nums) + 1)\n",
    "\n",
    "        for i in range(len(nums)-2, -1, -1):\n",
    "            if nums[i] <= nums[i + 1]:\n",
    "                suf[i] = suf[i+1] + 1\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if  0 < i <= n-2 and  pre[i-1] >= k and suf[i+1] >= k:\n",
    "                res.append(i)\n",
    "            if nums[i] <= nums[i-1]:\n",
    "                pre[i] = pre[i-1] + 1\n",
    "\n",
    "        return res           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left, right = [0] * n, [0] * n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if nums[i] <= nums[i-1]:\n",
    "                left[i] = left[i-1] + 1\n",
    "            if nums[n-i-1] <= nums[n-i]:\n",
    "                right[n-i-1] = right[n-i] + 1\n",
    "        print(left, right)\n",
    "        \n",
    "        return [i for i in range(k, n-k) if left[i-1] >= k-1 and right[i+1] >= k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        left=[1]*n\n",
    "        right=[1]*n        \n",
    "        res=[]\n",
    "        for i in range(1,n):\n",
    "            if nums[i-1]>=nums[i]:\n",
    "                left[i]=left[i-1]+1\n",
    "            if nums[n-i]>=nums[n-i-1]:\n",
    "                right[n-i-1]=right[n-i]+1\n",
    "        print (left)\n",
    "        print (right)\n",
    "        for i in range(k,n-k):\n",
    "            if  left[i-1]>=k and right[i+1]>=k:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        up = [1]*n\n",
    "        down = [1]*n\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                up[i]=up[i-1]+1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if nums[i]<=nums[i+1]:\n",
    "                down[i]=down[i+1]+1\n",
    "        \n",
    "        print(up)\n",
    "        print(down)\n",
    "\n",
    "        return [i for i in range(k,n-k) if up[i-1]>=k and down[i+1]>=k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodIndices(self, nums: List[int], k: int) -> List[int]:\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        \n",
    "        right = [1] * n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if nums[i] <= nums[i+1]:\n",
    "                right[i] = right[i+1] + 1\n",
    "        \n",
    "        left = [1] * n\n",
    "        for i in range(1,n):\n",
    "            if nums[i] <= nums[i-1]:\n",
    "                left[i] = left[i-1] + 1\n",
    "        \n",
    "        print(left)\n",
    "        print(right)\n",
    "        for i in range(k,n-k):\n",
    "            if left[i-1] >= k and right[i+1] >= k:\n",
    "                ans.append(i)\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
